/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2024-02-03
 * Time: 14:51
 *
 * https://www.nowcoder.com/share/jump/7745334641706943117230
 */
public class BM66 {


    public String LCS(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        // dp[i][j] 表示在 str1 中以第 i 个字符结尾在 str2 中以第 j 个字符结尾时的公共子串长度
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 记录最长子串的长度
        int maxLen = 0;
        // 记录结束位置
        int pos = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    // 长度加 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 不再连续，断开从 0 开始
                    dp[i][j] = 0;
                }
                // 更新最长
                if (maxLen < dp[i][j]) {
                    maxLen = dp[i][j];
                    // 因为是二者公共的，所以仅仅记录一个即可
                    pos = i - 1;
                }
            }
        }
        // 根据长度和结束位置，推出公共的子串范围
        return str1.substring(pos - maxLen + 1, pos + 1);
    }
}
